package LeetCode.month01.day19;

import java.util.Arrays;

public class No05 {
    public static void main(String[] args) {
        //System.out.println(longestPalindrome("adcbcca"));
        System.out.println(longestPalindrome("bbbbb"));
        //System.out.println(longestPalindrome("adcbcca"));
    }
    public static int expand(String s,int left,int right){
        while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
            left--;
            right++;
        }
        return right-left-1;
    }
    public static String longestPalindrome(String s) {
        //中心拓展法
        if(s.length()==1)return s;
        int len = s.length();
        int left= 0,right=0;
        for (int i = 0; i < len; i++) {
            int len1 =expand(s,i,i);
            int len2 =expand(s,i,i+1);
            int max = Math.max(len1,len2);
            if(max>right-left){
                left = i-(max-1)/2;
                right= i+max/2;
            }
        }
        return s.substring(left,right+1);


        //动态规划 dp代表从当前位置j开始到结束位置i是不是回文字符串
//        int left= 0,right=0;
//        int max = 1;
//        boolean[] dp = new boolean[s.length()];
//        for (int i = 0; i < s.length(); i++) {
//            for (int j = 0; j <= i; j++) {
//                if(i==j){
//                    dp[j]=true;
//                }else if(j+1==i){
//                    dp[j]=s.charAt(j)==s.charAt(i);
//                }else{
//                    dp[j]=s.charAt(j)==s.charAt(i)?dp[j+1]:false;
//                }
//                if(dp[j]&&i-j>right-left){
//                    left = j;
//                    right = i;
//                }
//            }
//        }
//        return s.substring(left,right+1);
    }
}
